package com.peng.leetcode.graph;

import java.util.*;

/**
 * NetworkDelayTime1
 *
 * 743. 网络延迟时间
 * 
 * 给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
 *
 * 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
 *
 * 链接：https://leetcode-cn.com/problems/network-delay-time
 *
 * @author: lupeng6
 * @create: 2021/2/19 19:35
 */
public class NetworkDelayTime1 {

    public static void main(String[] args) {
        int[][] times = {{2,1,1},{2,3,1},{3,4,1}};
        int n = 4, k = 2;
        System.out.println(new NetworkDelayTime1().networkDelayTime(times, n, k));
    }

    /**
     * 1. 初始化邻居节点
     * 2. 然后从指定节点出发，找下一个邻居节点。优先选择耗时最小的节点，借助优先队列（小顶堆）
     * 3. 并且需要记录下访问过的节点和耗时
     * 4. 然后依次访问完所有节点
     *
     * @author lupeng6
     * @date 2021/2/19 19:38
     */
    public int networkDelayTime(int[][] times, int N, int K) {
        //初始化邻居图
        Map<Integer, List<Vertex>> adjacency = new HashMap<>();
        for (int[] time : times) {
            int source = time[0];
            int target = time[1];
            int consume = time[2];
            Vertex vertex = new Vertex(source, target, consume);
            adjacency.putIfAbsent(source, new ArrayList<>());
            adjacency.get(source).add(vertex);
        }

        //记录访问节点耗时
        //优先队列
        Map<Integer, Integer> consumeMap = new HashMap<>();
        PriorityQueue<Vertex> minHeap = new PriorityQueue<>();

        minHeap.offer(new Vertex(K, K, 0));

        while (!minHeap.isEmpty()) {
            Vertex vertex = minHeap.poll();
            int source = vertex.target;
            int consumeTime = vertex.time;

            if (consumeMap.containsKey(source)) {
                continue;
            }

            consumeMap.put(source, consumeTime);

            List<Vertex> nextVertices = adjacency.get(source);
            if (nextVertices != null && !nextVertices.isEmpty()) {
                for (Vertex nextVertex : nextVertices) {
                    if (consumeMap.containsKey(nextVertex.target)) {
                        continue;
                    }

                    minHeap.offer(new Vertex(nextVertex.source, nextVertex.target, nextVertex.time + consumeTime));
                }
            }
        }

        if (consumeMap.size() != N) {
            return -1;
        }
        int ans = 0;
        for (Integer value : consumeMap.values()) {
            ans = Math.max(value, ans);
        }
        return ans;
    }

    static class Vertex implements Comparable<Vertex> {
        int source;
        int target;
        int time;

        public Vertex(int source, int target, int time) {
            this.source = source;
            this.target = target;
            this.time = time;
        }

        @Override
        public int compareTo(Vertex vertex) {
            return Integer.compare(time, vertex.time);
        }
    }
}
